Synchronization is a function that provides or maintains consistency between data sets. For example, a desktop computer may have desktop data sets regarding personal information management (“PIM”). A user of that desktop computer may desire to use that PIM data when she is away from her desktop computer. Therefore, she may desire access to the PIM data while using a laptop computer or a personal digital assistant (“PDA”) such as a phone or other device like a miniature device. In order to accommodate that desire, her laptop computer and PDA may each carry PIM data sets that correspond to the PIM data sets on the desktop computer. The role of the synchronization function is to give the user a common view of her data on each device. This role is generally accomplished by synchronization events when two or more of the devices synchronize.
A common technique for synchronizing devices is by using snapshots of data at a point in time and comparing current data to the snapshot to determine what has changed. For illustration purposes, refer to FIG. 1 where there is shown a model for two devices, a desktop computer 100 and a portable computer 110. Desktop computer has PIM database 101, which keeps current information for PIM data sets that are edited or added on the desktop computer 100. Desktop computer 100 also has desktop snapshot database, which is a snapshot of the PIM data sets taken at some point in time but typically the time of a prior synchronization (perhaps, the most recent synchronization). Similarly, portable computer 110 has portable database 111 for current PIM data. Having these structures in place, we may attempt to synchronize desktop 100 and portable 110. Typical synchronization occurs by comparing both portable database 111 and desktop database 101 with snapshot database 102. During the compare operation, we can then assemble a list of data items that are new or changed in the active databases 101 and 111 as compared to database 102. Finally, to finish out the synchronization, the list of new and changed data may be used to update all three databases 101, 102, and 111.
A problem occurs in the described synchronization process when corresponding data is changed on both the desktop and the portable. For example, if sometime prior to synchronization Jane Doe's phone number was changed to 877-555-5555 on the Desktop and 800-555-5555 on the portable. During the compare operation (or at another time) the synchronizing system will notice this discrepancy and identify a conflict. In the current art, there is generally no elegant way to resolve this conflict with certainty. Some solutions present an interface to the user and ask her to choose between the two options. Unfortunately, even the user may not remember which piece of data is correct. Other solutions simply create duplicate entries in each database (one with each of the possible data items).
The problem is exacerbated if there are more than two devices carrying the corresponding data sets. For example, referring to FIG. 1, assume that after synchronizing with portable 110, desktop 100 attempts to synchronize with PDA 120. During synchronization, we may discover that PDA 120 carries Jane Doe's phone number as 888-555-555. Unfortunately, in the prior art, we once again have no elegant solution for determining the correct result with certainty. Furthermore, even if we could determine the correct result at this time (e.g. by the user, who remembers), we may be unable to stop the system from having the same problem again the next time portable 110 is synchronized.
Finally, the problem may be generalized for peer-to-peer systems with 3 or more peers. That generalization is that, if peers may synchronize with each other 2 at a time, and a conflict arises there is no way to know if one of the peers carries a more up-to-date data. It is noteworthy, that a time stamp cannot resolve the conflict with certainty. This is because as a matter of practical human usage, if two corresponding data items have been changed over the past days or months, that does not necessarily mean that the second change is correct. This is especially true if the second change occurred as the result of synchronization with another peer (such “another peer” may have received its data change long ago). Therefore, in the peer-to-peer situation, we would be unable to determine if a detected conflict is, on the one hand, a true conflict, or on the other hand, an apparent conflict that could be verifiably resolved if we understood the history of the data.
Other and related prior art techniques for synchronization may be found in the following U.S. Pat. No. 5,710,922 Method for synchronizing and archiving information between computer systems, which is incorporated herein by reference. In addition, the following pending applications “A Method of Synchronizing Between Three or More Devices” by Toby Paterson and Jerome Lebel, having Ser. No. 10/853,306 and filed May 24, 2004 and “A Method of Synchronizing” by Toby Patterson and Jerome Lebel, having Ser. No. 10/852,926 and filed May 24, 2004 are hereby incorporated by reference.
In view of the discussion herein as well as the other problems existing in the prior art, certain embodiments of the invention propose a synchronization system with three goals: (i) to properly synchronize all non-conflicting data; (ii) to detect true conflicts and only present an interface to the user for resolving same if the conflict is true; (iii) to avoid asking an user twice to resolve the same conflict for the same datum.
Applying these goals to the prior art, we may observe that existing synchronization systems meet the first goal in that they generally can accurately synchronize non-conflicting data. However, to satisfy the second and third goals, some type of meta-data must be retained, for example, our reference to a time stamp above. While some prior art systems attempt to use meta-data to accomplish these goals, none fully succeeds.
In view of the discussion herein as well as the other problems existing in the prior art, certain embodiments of the present disclosure also propose: (i) a synchronization system capable of hubless or decentralized syncing in a peer-to-peer system where any number of users and devices can come and go without coordination and no one machine or device needs to know the existence of all other machines or devices; and (ii) a synchronization system wherein the information that the system needs to know (i.e., synchronization metadata) is associated with each datum and is lightweight; and (iii) does not require a universal time stamp or coordinated logical clock common to all peers.